SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Pathwidth</title>

</head>

Pathwidth

</h1>

</header>

In <a href="Graph_theory" title="Graph theory">graph theory</a>, a path decomposition of a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> G is, informally, a representation of G as a "thickened" <a href="Path_graph" title="Path graph">path graph</a>,<a href="#cite_note-1">[1]</a> and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of <a href="Subset" title="Subset">subsets</a> of <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets,<a href="#cite_note-rs83-2">[2]</a> and the pathwidth is one less than the size of the largest set in such a decomposition.

Pathwidth is also known as interval thickness (one less than the <a href="Maximum_clique" class="mw-redirect" title="Maximum clique">maximum clique</a> size in an <a href="Interval_graph" title="Interval graph">interval</a> <a href="Glossary_of_graph_theory#Subgraphs" title="Glossary of graph theory">supergraph</a> of G), vertex separation number, or node searching number.<a href="#cite_note-3">[3]</a>

Pathwidth and path-decompositions are closely analogous to <a href="Treewidth" title="Treewidth">treewidth</a> and <a href="Tree_decomposition" title="Tree decomposition">tree decompositions</a>. They play a key role in the theory of <a href="Graph_minor" title="Graph minor">graph minors</a>: the families of graphs that are closed under <a href="Graph_minor" title="Graph minor">graph minors</a> and do not include all <a href="Tree_(graph_theory)" title="Tree (graph theory)">forests</a> may be characterized as having bounded pathwidth,<a href="#cite_note-rs83-2">[2]</a> and the "vortices" appearing in the general <a href="Graph_structure_theorem" title="Graph structure theorem">structure theory for minor-closed graph families</a> have bounded pathwidth.<a href="#cite_note-Robertson_2003-4">[4]</a> Pathwidth, and graphs of bounded pathwidth, also have applications in <a href="VLSI" class="mw-redirect" title="VLSI">VLSI</a> design, <a href="Graph_drawing" title="Graph drawing">graph drawing</a>, and <a href="Computational_linguistics" title="Computational linguistics">computational linguistics</a>.

It is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> to find the pathwidth of arbitrary graphs, or even to approximate it accurately.<a href="#cite_note-npc-5">[5]</a><a href="#cite_note-bghk92-6">[6]</a> However, the problem is <a href="Fixed-parameter_tractable" class="mw-redirect" title="Fixed-parameter tractable">fixed-parameter tractable</a>: testing whether a graph has pathwidth k can be solved in an amount of time that depends linearly on the size of the graph but superexponentially on k.<a href="#cite_note-bounded-tw-algs-7">[7]</a> Additionally, for several special classes of graphs, such as <a href="Tree_(graph_theory)" title="Tree (graph theory)">trees</a>, the pathwidth may be computed in polynomial time without dependence on k.<a href="#cite_note-FOOTNOTEBodlaender1994-8">[8]</a><a href="#cite_note-tree-algs-9">[9]</a>

Many problems in graph algorithms may be solved efficiently on graphs of bounded pathwidth, by using <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> on a path-decomposition of the graph.<a href="#cite_note-Arnborg_1985-10">[10]</a> Path decomposition may also be used to measure the <a href="Space_complexity" title="Space complexity">space complexity</a> of dynamic programming algorithms on graphs of bounded <a href="Treewidth" title="Treewidth">treewidth</a>.<a href="#cite_note-apt00-11">[11]</a>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

In the first of their famous series of papers on <a href="Graph_minor" title="Graph minor">graph minors</a>, <a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Neil Robertson</a> and <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Paul Seymour</a> (<a href="#CITEREFRobertsonSeymour1983">1983</a>) define a path-decomposition of a graph G to be a sequence of subsets Xi of vertices of G, with two properties:

<ol><li>For each edge of G, there exists an i such that both endpoints of the edge belong to subset Xi, and</li>

<li>For every three indices i ≤ j ≤ k, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}\cap X_{k}\subseteq X_{j}.}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i}\cap X_{k}\subseteq X_{j}.}</annotation>

</semantics>

</math><img src="./53e92de73a57f8d4cc913f52b17bb2dded74067f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.899ex; height:2.843ex;" alt="{\displaystyle X_{i}\cap X_{k}\subseteq X_{j}.}" loading="lazy"></li></ol>

The second of these two properties is equivalent to requiring that the subsets containing any particular vertex form a contiguous subsequence of the whole sequence. In the language of the later papers in Robertson and Seymour's graph minor series, a path-decomposition is a <a href="Tree_decomposition" title="Tree decomposition">tree decomposition</a> (X,T) in which the underlying tree T of the decomposition is a <a href="Path_graph" title="Path graph">path graph</a>.

The width of a path-decomposition is defined in the same way as for tree-decompositions, as maxi |Xi| − 1, and the pathwidth of G is the minimum width of any path-decomposition of G. The subtraction of one from the size of Xi in this definition makes little difference in most applications of pathwidth, but is used to make the pathwidth of a <a href="Path_graph" title="Path graph">path graph</a> be equal to one.

<div class="mw-heading mw-heading2"><h2 id="Alternative_characterizations">Alternative characterizations</h2></div>

As <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a> describes, pathwidth can be characterized in many equivalent ways.

<div class="mw-heading mw-heading3"><h3 id="Gluing_sequences">Gluing sequences</h3></div>

A path decomposition can be described as a sequence of graphs Gi that are glued together by identifying pairs of vertices from consecutive graphs in the sequence, such that the result of performing all of these gluings is G. The graphs Gi may be taken as the <a href="Induced_subgraph" title="Induced subgraph">induced subgraphs</a> of the sets Xi in the first definition of path decompositions, with two vertices in successive induced subgraphs being glued together when they are induced by the same vertex in G, and in the other direction one may recover the sets Xi as the vertex sets of the graphs Gi. The width of the path decomposition is then one less than the maximum number of vertices in one of the graphs Gi.<a href="#cite_note-rs83-2">[2]</a>

<div class="mw-heading mw-heading3"><h3 id="Interval_thickness">Interval thickness</h3></div>

The pathwidth of any graph G is equal to one less than the smallest clique number of an <a href="Interval_graph" title="Interval graph">interval graph</a> that contains G as a subgraph.<a href="#cite_note-12">[12]</a> That is, for every path decomposition of G one can find an interval supergraph of G, and for every interval supergraph of G one can find a path decomposition of G, such that the width of the decomposition is one less than the clique number of the interval graph.

In one direction, suppose a path decomposition of G is given. Then one may represent the nodes of the decomposition as points on a line (in path order) and represent each vertex v as a closed interval having these points as endpoints. In this way, the path decomposition nodes containing v correspond to the representative points in the interval for v. The <a href="Intersection_graph" title="Intersection graph">intersection graph</a> of the intervals formed from the vertices of G is an interval graph that contains G as a subgraph. Its maximal cliques are given by the sets of intervals containing the representative points, and its maximum clique size is one plus the pathwidth of G.

In the other direction, if G is a subgraph of an interval graph with clique number p + 1, then G has a path decomposition of width p whose nodes are given by the <a href="Maximal_clique" class="mw-redirect" title="Maximal clique">maximal cliques</a> of the interval graph. For instance, the interval graph shown with its interval representation in the figure has a path decomposition with five nodes, corresponding to its five maximal cliques ABC, ACD, CDE, CDF, and FG; the maximum clique size is three and the width of this path decomposition is two.

This equivalence between pathwidth and interval thickness is closely analogous to the equivalence between treewidth and the minimum clique number (minus one) of a <a href="Chordal_graph" title="Chordal graph">chordal graph</a> of which the given graph is a subgraph. Interval graphs are a special case of chordal graphs, and chordal graphs can be represented as intersection graphs of subtrees of a common tree generalizing the way that interval graphs are intersection graphs of subpaths of a path.

<div class="mw-heading mw-heading3"><h3 id="Vertex_separation_number">Vertex separation number</h3></div>

The vertex separation number of G with respect to a <a href="Linear_order" class="mw-redirect" title="Linear order">linear ordering</a> of the vertices of G is the smallest number s such that, for each vertex v, at most s vertices are earlier than v in the ordering but that have v or a later vertex as a neighbor.

The vertex separation number of G is the smallest vertex separation number of G with respect to any linear ordering of G. The vertex separation number was defined by <a href="#CITEREFEllisSudboroughTurner1983">Ellis, Sudborough & Turner (1983)</a>, and is equal to the pathwidth of G.<a href="#cite_note-13">[13]</a>

This follows from the earlier equivalence with interval graph clique numbers: if G is a subgraph of an interval graph I, represented (as in the figure) in such a way that all interval endpoints are distinct, then the ordering of the left endpoints of the intervals of I has vertex separation number one less than the clique number of I. And in the other direction, from a linear ordering of G one may derive an interval representation in which the left endpoint of the interval for a vertex v is its position in the ordering and the right endpoint is the position of the neighbor of v that comes last in the ordering.

<div class="mw-heading mw-heading3"><h3 id="Node_searching_number">Node searching number</h3></div>

The node searching game on a graph is a form of <a href="Pursuit%E2%80%93evasion" title="Pursuit–evasion">pursuit–evasion</a> in which a set of searchers collaborate to track down a fugitive hiding in a graph. The searchers are placed on vertices of the graph while the fugitive may be in any edge of the graph, and the fugitive's location and moves are hidden from the searchers. In each turn, some or all of the searchers may move (arbitrarily, not necessarily along edges) from one vertex to another, and then the fugitive may move along any path in the graph that does not pass through a searcher-occupied vertex. The fugitive is caught when both endpoints of his edge are occupied by searchers. The node searching number of a graph is the minimum number of searchers needed to ensure that the fugitive can be guaranteed to be caught, no matter how he moves. As <a href="#CITEREFKirousisPapadimitriou1985">Kirousis & Papadimitriou (1985)</a> show, the node searching number of a graph equals its interval thickness. The optimal strategy for the searchers is to move the searchers so that in successive turns they form the separating sets of a linear ordering with minimal vertex separation number.

<div class="mw-heading mw-heading2"><h2 id="Bounds">Bounds</h2></div>

Every n-vertex graph with pathwidth k has at most k(n − k + (k − 1)/2) edges, and the <a href="Maximal_element" class="mw-redirect" title="Maximal element">maximal</a> pathwidth-k graphs (graphs to which no more edges can be added without increasing the pathwidth) have exactly this many edges. A maximal pathwidth-k graph must be either a k-path or a k-caterpillar, two special kinds of <a href="K-tree" title="K-tree">k-tree</a>. A k-tree is a <a href="Chordal_graph" title="Chordal graph">chordal graph</a> with exactly n − k <a href="Maximal_clique" class="mw-redirect" title="Maximal clique">maximal cliques</a>, each containing k + 1 vertices; in a k-tree that is not itself a (k + 1)-clique, each maximal clique either separates the graph into two or more components, or it contains a single leaf vertex, a vertex that belongs to only a single maximal clique. A k-path is a k-tree with at most two k-leaves, and a k-caterpillar is a k-tree that can be partitioned into a k-path and a set of k-leaves each adjacent to a separator k-clique of the k-path. In particular the maximal graphs of pathwidth one are exactly the <a href="Caterpillar_tree" title="Caterpillar tree">caterpillar trees</a>.<a href="#cite_note-14">[14]</a>

Since path-decompositions are a special case of tree-decompositions, the pathwidth of any graph is greater than or equal to its <a href="Treewidth" title="Treewidth">treewidth</a>. The pathwidth is also less than or equal to the <a href="Cutwidth" title="Cutwidth">cutwidth</a>, the minimum number of edges that cross any cut between lower-numbered and higher-numbered vertices in an optimal linear arrangement of the vertices of a graph; this follows because the vertex separation number, the number of lower-numbered vertices with higher-numbered neighbors, can at most equal the number of cut edges.<a href="#cite_note-15">[15]</a> For similar reasons, the cutwidth is at most the pathwidth times the <a href="Degree_(graph_theory)" title="Degree (graph theory)">maximum degree</a> of the vertices in a given graph.<a href="#cite_note-16">[16]</a>

Any n-vertex <a href="Tree_(graph_theory)" title="Tree (graph theory)">forest</a> has pathwidth O(log n).<a href="#cite_note-17">[17]</a> For, in a forest, one can always find a constant number of vertices the removal of which leaves a forest that can be partitioned into two smaller subforests with at most <style data-mw-deduplicate="TemplateStyles:r1154941027">

/* start https://en.wikipedia.org/ */

.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>2n⁄3 vertices each. A linear arrangement formed by recursively partitioning each of these two subforests, placing the separating vertices between them, has logarithmic vertex searching number. The same technique, applied to a tree-decomposition of a graph, shows that, if the treewidth of an n-vertex graph G is t, then the pathwidth of G is O(t log n).<a href="#cite_note-18">[18]</a> Since <a href="Outerplanar_graph" title="Outerplanar graph">outerplanar graphs</a>, <a href="Series%E2%80%93parallel_graph" title="Series–parallel graph">series–parallel graphs</a>, and <a href="Halin_graph" title="Halin graph">Halin graphs</a> all have bounded treewidth, they all also have at most logarithmic pathwidth.

As well as its relations to treewidth, pathwidth is also related to <a href="Clique-width" title="Clique-width">clique-width</a> and <a href="Cutwidth" title="Cutwidth">cutwidth</a>, via <a href="Line_graph" title="Line graph">line graphs</a>; the line graph L(G) of a graph G has a vertex for each edge of G and two vertices in L(G) are adjacent when the corresponding two edges of G share an endpoint. Any family of graphs has bounded pathwidth if and only if its line graphs have bounded linear clique-width, where linear clique-width replaces the disjoint union operation from clique-width with the operation of adjoining a single new vertex.<a href="#cite_note-19">[19]</a> If a connected graph with three or more vertices has maximum degree three, then its cutwidth equals the vertex separation number of its line graph.<a href="#cite_note-20">[20]</a>

In any <a href="Planar_graph" title="Planar graph">planar graph</a>, the pathwidth is at most proportional to the square root of the number of vertices.<a href="#cite_note-21">[21]</a> One way to find a path-decomposition with this width is (similarly to the logarithmic-width path-decomposition of forests described above) to use the <a href="Planar_separator_theorem" title="Planar separator theorem">planar separator theorem</a> to find a set of O(√n) vertices the removal of which separates the graph into two subgraphs of at most 2n⁄3 vertices each, and concatenate recursively-constructed path decompositions for each of these two subgraphs. The same technique applies to any class of graphs for which a similar separator theorem holds.<a href="#cite_note-22">[22]</a> Since, like planar graphs, the graphs in any fixed minor-closed graph family have separators of size O(√n),<a href="#cite_note-23">[23]</a> it follows that the pathwidth of the graphs in any fixed minor-closed family is again O(√n). For some classes of planar graphs, the pathwidth of the graph and the pathwidth of its <a href="Dual_graph" title="Dual graph">dual graph</a> must be within a constant factor of each other: bounds of this form are known for biconnected outerplanar graphs<a href="#cite_note-24">[24]</a> and for polyhedral graphs.<a href="#cite_note-25">[25]</a> For 2-connected planar graphs, the pathwidth of the dual graph is less than the pathwidth of the line graph.<a href="#cite_note-26">[26]</a> It remains open whether the pathwidth of a planar graph and its dual are always within a constant factor of each other in the remaining cases.

In some classes of graphs, it has been proven that the pathwidth and treewidth are always equal to each other: this is true for <a href="Cograph" title="Cograph">cographs</a>,<a href="#cite_note-bm90-27">[27]</a> <a href="Permutation_graph" title="Permutation graph">permutation graphs</a>,<a href="#cite_note-bkk93-28">[28]</a> the <a href="Complement_graph" title="Complement graph">complements</a> of <a href="Comparability_graph" title="Comparability graph">comparability graphs</a>,<a href="#cite_note-hm94-29">[29]</a> and the comparability graphs of <a href="Interval_order" title="Interval order">interval orders</a>.<a href="#cite_note-g95-30">[30]</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output .unsolved{margin:0.5em 0 1em 1em;border:1px solid #a2a9b1;padding:0.35em 0.35em 0.35em 2.2em;background-color:var(--background-color-interactive-subtle);background-image:url("./mw/Question%2C_Web_Fundamentals.svg");background-position:top 50%left 0.35em;background-size:1.5em;background-repeat:no-repeat}@media(min-width:720px){.mw-parser-output .unsolved{clear:right;float:right;max-width:25%}}.mw-parser-output .unsolved-label{font-weight:bold}.mw-parser-output .unsolved-body{margin:0.35em;font-style:italic}.mw-parser-output .unsolved-more{font-size:smaller}

/* end https://en.wikipedia.org/ */

</style>

<div>Unsolved problem in mathematics</div>

<div class="unsolved-body">What is the largest possible pathwidth of an n-vertex <a href="Cubic_graph" title="Cubic graph">cubic graph</a>?</div>

<div class="unsolved-more"><a href="List_of_unsolved_problems_in_mathematics" title="List of unsolved problems in mathematics">More unsolved problems in mathematics</a></div>

</div>

In any <a href="Cubic_graph" title="Cubic graph">cubic graph</a>, or more generally any graph with maximum vertex degree three, the pathwidth is at most n⁄6 + o(n), where n is the number of vertices in the graph. There exist cubic graphs with pathwidth 0.082n, but it is not known how to reduce this gap between this <a href="Lower_bound" class="mw-redirect" title="Lower bound">lower bound</a> and the n⁄6 upper bound.<a href="#cite_note-fh06-31">[31]</a>

<div class="mw-heading mw-heading2"><h2 id="Computing_path-decompositions">Computing path-decompositions</h2></div>

It is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> to determine whether the pathwidth of a given graph is at most k, when k is a variable given as part of the input.<a href="#cite_note-npc-5">[5]</a> The best known worst-case time bounds for computing the pathwidth of arbitrary n-vertex graphs are of the form O(2nnc) for some constant c.<a href="#cite_note-32">[32]</a> Nevertheless, several algorithms are known to compute path-decompositions more efficiently when the pathwidth is small, when the class of input graphs is limited, or approximately.

<div class="mw-heading mw-heading3"><h3 id="Fixed-parameter_tractability">Fixed-parameter tractability</h3></div>

Pathwidth is <a href="Fixed-parameter_tractable" class="mw-redirect" title="Fixed-parameter tractable">fixed-parameter tractable</a>: for any constant k, it is possible to test whether the pathwidth is at most k, and if so to find a path-decomposition of width k, in linear time.<a href="#cite_note-bounded-tw-algs-7">[7]</a> In general, these algorithms operate in two phases. In the first phase, the assumption that the graph has pathwidth k is used to find a path-decomposition or tree-decomposition that is not optimal, but whose width can be bounded as a function of k. In the second phase, a <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> algorithm is applied to this decomposition in order to find the optimal decomposition.

However, the time bounds for known algorithms of this type are exponential in k2, impractical except for the smallest values of k.<a href="#cite_note-33">[33]</a> For the case k = 2 an explicit linear-time algorithm based on a structural decomposition of pathwidth-2 graphs is given by <a href="#CITEREFde_Fluiter1997">de Fluiter (1997)</a>.

<div class="mw-heading mw-heading3"><h3 id="Special_classes_of_graphs">Special classes of graphs</h3></div>

<a href="#CITEREFBodlaender1994">Bodlaender (1994)</a> surveys the complexity of computing the pathwidth on various special classes of graphs. Determining whether the pathwidth of a graph G is at most k remains NP-complete when G is restricted to bounded-degree graphs,<a href="#cite_note-ms88-34">[34]</a> <a href="Planar_graph" title="Planar graph">planar graphs</a>,<a href="#cite_note-ms88-34">[34]</a> planar graphs of bounded degree,<a href="#cite_note-ms88-34">[34]</a> <a href="Chordal_graph" title="Chordal graph">chordal graphs</a>,<a href="#cite_note-35">[35]</a> chordal dominoes,<a href="#cite_note-36">[36]</a> the <a href="Complement_graph" title="Complement graph">complements</a> of <a href="Comparability_graph" title="Comparability graph">comparability graphs</a>,<a href="#cite_note-hm94-29">[29]</a>

and <a href="Bipartite_graph" title="Bipartite graph">bipartite</a> <a href="Distance-hereditary_graph" title="Distance-hereditary graph">distance-hereditary graphs</a>.<a href="#cite_note-kbmk-37">[37]</a> It follows immediately that it is also NP-complete for the graph families that contain the bipartite distance-hereditary graphs, including the bipartite graphs, chordal bipartite graphs, distance-hereditary graphs, and <a href="Circle_graph" title="Circle graph">circle graphs</a>.<a href="#cite_note-kbmk-37">[37]</a>

However, the pathwidth may be computed in linear time for trees and forests.<a href="#cite_note-tree-algs-9">[9]</a> It may also be computed in polynomial time for graphs of bounded treewidth including <a href="Series%E2%80%93parallel_graph" title="Series–parallel graph">series–parallel graphs</a>, <a href="Outerplanar_graph" title="Outerplanar graph">outerplanar graphs</a>, and <a href="Halin_graph" title="Halin graph">Halin graphs</a>,<a href="#cite_note-bounded-tw-algs-7">[7]</a> as well as for <a href="Split_graph" title="Split graph">split graphs</a>,<a href="#cite_note-38">[38]</a> for the complements of chordal graphs,<a href="#cite_note-39">[39]</a> for <a href="Permutation_graph" title="Permutation graph">permutation graphs</a>,<a href="#cite_note-bkk93-28">[28]</a> for <a href="Cograph" title="Cograph">cographs</a>,<a href="#cite_note-bm90-27">[27]</a> for <a href="Circular-arc_graph" title="Circular-arc graph">circular-arc graphs</a>,<a href="#cite_note-40">[40]</a> for the comparability graphs of interval orders,<a href="#cite_note-g95-30">[30]</a> and of course for <a href="Interval_graph" title="Interval graph">interval graphs</a> themselves, since in that case the pathwidth is just one less than the maximum number of intervals covering any point in an interval representation of the graph.

<div class="mw-heading mw-heading3"><h3 id="Approximation_algorithms">Approximation algorithms</h3></div>

It is NP-hard to approximate the pathwidth of a graph to within an additive constant.<a href="#cite_note-bghk92-6">[6]</a>

The best known <a href="Approximation_ratio" class="mw-redirect" title="Approximation ratio">approximation ratio</a> of a polynomial time approximation algorithm for pathwidth is O((log n)3/2).<a href="#cite_note-41">[41]</a>

For earlier approximation algorithms for pathwidth, see <a href="#CITEREFBodlaenderGilbertHafsteinssonKloks1992">Bodlaender et al. (1992)</a> and <a href="#CITEREFGuha2000">Guha (2000)</a>. For approximations on restricted classes of graphs, see <a href="#CITEREFKloksBodlaender1992">Kloks & Bodlaender (1992)</a>.

<div class="mw-heading mw-heading2"><h2 id="Graph_minors">Graph minors</h2></div>

A <a href="Graph_minor" title="Graph minor">minor</a> of a graph G is another graph formed from G by contracting edges, removing edges, and removing vertices. Graph minors have a deep theory in which several important results involve pathwidth.

<div class="mw-heading mw-heading3"><h3 id="Excluding_a_forest">Excluding a forest</h3></div>

If a family F of graphs is closed under taking minors (every minor of a member of F is also in F), then by the <a href="Robertson%E2%80%93Seymour_theorem" title="Robertson–Seymour theorem">Robertson–Seymour theorem</a> F can be characterized as the graphs that do not have any minor in X, where X is a finite set of <a href="Forbidden_graph_characterization" title="Forbidden graph characterization">forbidden minors</a>.<a href="#cite_note-gm20-42">[42]</a> For instance, <a href="Wagner's_theorem" title="Wagner's theorem">Wagner's theorem</a> states that the <a href="Planar_graph" title="Planar graph">planar graphs</a> are the graphs that have neither the <a href="Complete_graph" title="Complete graph">complete graph</a> K5 nor the <a href="Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graph</a> K3,3 as minors. In many cases, the properties of F and the properties of X are closely related, and the first such result of this type was by <a href="#CITEREFRobertsonSeymour1983">Robertson & Seymour (1983)</a>,<a href="#cite_note-rs83-2">[2]</a> and relates bounded pathwidth with the existence of a <a href="Tree_(graph_theory)" title="Tree (graph theory)">forest</a> in the family of forbidden minors. Specifically, define a family F of graphs to have bounded pathwidth if there exists a constant p such that every graph in F has pathwidth at most p. Then, a minor-closed family F has bounded pathwidth if and only if the set X of forbidden minors for F includes at least one forest.

In one direction, this result is straightforward to prove: if X does not include at least one forest, then the X-minor-free graphs do not have bounded pathwidth. For, in this case, the X-minor-free graphs include all forests, and in particular they include the <a href="Perfect_binary_tree" class="mw-redirect" title="Perfect binary tree">perfect binary trees</a>. But a perfect binary tree with 2k + 1 levels has pathwidth k, so in this case the X-minor-free-graphs have unbounded pathwidth. In the other direction, if X contains an n-vertex forest, then the X-minor-free graphs have pathwidth at most n − 2.<a href="#cite_note-43">[43]</a>

<div class="mw-heading mw-heading3"><h3 id="Obstructions_to_bounded_pathwidth">Obstructions to bounded pathwidth</h3></div>

The property of having pathwidth at most p is, itself, closed under taking minors: if G has a path-decomposition with width at most p, then the same path-decomposition remains valid if any edge is removed from G, and any vertex can be removed from G and from its path-decomposition without increasing the width. Contraction of an edge, also, can be accomplished without increasing the width of the decomposition, by merging the sub-paths representing the two endpoints of the contracted edge. Therefore, the graphs of pathwidth at most p can be characterized by a set Xp of excluded minors.<a href="#cite_note-gm20-42">[42]</a><a href="#cite_note-obstructions-44">[44]</a>

Although Xp necessarily includes at least one forest, it is not true that all graphs in Xp are forests: for instance, X1 consists of two graphs, a seven-vertex tree and the triangle K3. However, the set of trees in Xp may be precisely characterized: these trees are exactly the trees that can be formed from three trees in Xp − 1 by connecting a new root vertex by an edge to an arbitrarily chosen vertex in each of the three smaller trees. For instance, the seven-vertex tree in X1 is formed in this way from the two-vertex tree (a single edge) in X0. Based on this construction, the number of forbidden minors in Xp can be shown to be at least (p!)2.<a href="#cite_note-obstructions-44">[44]</a> The complete set X2 of forbidden minors for pathwidth-2 graphs has been computed; it contains 110 different graphs.<a href="#cite_note-45">[45]</a>

<div class="mw-heading mw-heading3"><h3 id="Structure_theory">Structure theory</h3></div>

The <a href="Graph_structure_theorem" title="Graph structure theorem">graph structure theorem</a> for minor-closed graph families states that, for any such family F, the graphs in F can be decomposed into <a href="Clique-sum" title="Clique-sum">clique-sums</a> of graphs that can be <a href="Graph_embedding" title="Graph embedding">embedded</a> onto surfaces of bounded <a href="Genus_(mathematics)" title="Genus (mathematics)">genus</a>, together with a bounded number of apexes and vortices for each component of the clique-sum. An apex is a vertex that may be adjacent to any other vertex in its component, while a vortex is a graph of bounded pathwidth that is glued into one of the faces of the bounded-genus embedding of a component. The cyclic ordering of the vertices around the face into which a vortex is embedded must be compatible with the path decomposition of the vortex, in the sense that breaking the cycle to form a linear ordering must lead to an ordering with bounded vertex separation number.<a href="#cite_note-Robertson_2003-4">[4]</a> This theory, in which pathwidth is intimately connected to arbitrary minor-closed graph families, has important algorithmic applications.<a href="#cite_note-46">[46]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

In <a href="VLSI" class="mw-redirect" title="VLSI">VLSI</a> design, the vertex separation problem was originally studied as a way to partition circuits into smaller subsystems, with a small number of components on the boundary between the subsystems.<a href="#cite_note-ms88-34">[34]</a>

<a href="#CITEREFOhtsukiMoriKuhKashiwabara1979">Ohtsuki et al. (1979)</a> use interval thickness to model the number of tracks needed in a one-dimensional layout of a VLSI circuit, formed by a set of modules that need to be interconnected by a system of nets. In their model, one forms a graph in which the vertices represent nets, and in which two vertices are connected by an edge if their nets both connect to the same module; that is, if the modules and nets are interpreted as forming the nodes and hyperedges of a <a href="Hypergraph" title="Hypergraph">hypergraph</a> then the graph formed from them is its <a href="Line_graph_of_a_hypergraph" title="Line graph of a hypergraph">line graph</a>. An interval representation of a supergraph of this line graph, together with a <a href="Graph_coloring" title="Graph coloring">coloring</a> of the supergraph, describes an arrangement of the nets along a system of horizontal tracks (one track per color) in such a way that the modules can be placed along the tracks in a linear order and connect to the appropriate nets. The fact that interval graphs are <a href="Perfect_graph" title="Perfect graph">perfect graphs</a><a href="#cite_note-47">[47]</a> implies that the number of colors needed, in an optimal arrangement of this type, is the same as the clique number of the interval completion of the net graph.

Gate matrix layout<a href="#cite_note-48">[48]</a> is a specific style of <a href="CMOS" title="CMOS">CMOS</a> VLSI layout for <a href="Boolean_logic" class="mw-redirect" title="Boolean logic">Boolean logic</a> circuits. In gate matrix layouts, signals are propagated along "lines" (vertical line segments) while each gate of the circuit is formed by a sequence of device features that lie along a horizontal line segment. Thus, the horizontal line segment for each gate must cross the vertical segments for each of the lines that form inputs or outputs of the gate. As in the layouts of <a href="#CITEREFOhtsukiMoriKuhKashiwabara1979">Ohtsuki et al. (1979)</a>, a layout of this type that minimizes the number of vertical tracks on which the lines are to be arranged can be found by computing the pathwidth of a graph that has the lines as its vertices and pairs of lines sharing a gate as its edges.<a href="#cite_note-fl89-49">[49]</a> The same algorithmic approach can also be used to model folding problems in <a href="Programmable_logic_array" title="Programmable logic array">programmable logic arrays</a>.<a href="#cite_note-50">[50]</a>

<div class="mw-heading mw-heading3"><h3 id="Graph_drawing">Graph drawing</h3></div>

Pathwidth has several applications to <a href="Graph_drawing" title="Graph drawing">graph drawing</a>:

<ul><li>The minimal graphs that have a given <a href="Crossing_number_(graph_theory)" title="Crossing number (graph theory)">crossing number</a> have pathwidth that is bounded by a function of their crossing number.<a href="#cite_note-h03-51">[51]</a></li>

<li>The number of parallel lines on which the vertices of a tree can be drawn with no edge crossings (under various natural restrictions on the ways that adjacent vertices can be placed with respect to the sequence of lines) is proportional to the pathwidth of the tree.<a href="#cite_note-52">[52]</a></li>

<li>A k-crossing h-layer drawing of a graph G is a placement of the vertices of G onto h distinct horizontal lines, with edges routed as monotonic polygonal paths between these lines, in such a way that there are at most k crossings. The graphs with such drawings have pathwidth that is bounded by a function of h and k. Therefore, when h and k are both constant, it is possible in linear time to determine whether a graph has a k-crossing h-layer drawing.<a href="#cite_note-dfkl08-53">[53]</a></li>

<li>A graph with n vertices and pathwidth p can be embedded into a three-dimensional grid of size p × p × n in such a way that no two edges (represented as straight line segments between grid points) intersect each other. Thus, graphs of bounded pathwidth have embeddings of this type with linear volume.<a href="#cite_note-54">[54]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Compiler_design">Compiler design</h3></div>

In the <a href="Compiler" title="Compiler">compilation</a> of <a href="High-level_programming_language" title="High-level programming language">high-level programming languages</a>, pathwidth arises in the problem of reordering sequences of straight-line code (that is, code with no <a href="Control_flow" title="Control flow">control flow</a> branches or loops) in such a way that all the values computed in the code can be <a href="Register_allocation" title="Register allocation">placed in machine registers</a> instead of having to be spilled into main memory. In this application, one represents the code to be compiled as a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> in which the nodes represent the input values to the code and the values computed by the operations within the code. An edge from node x to node y in this DAG represents the fact that value x is one of the inputs to operation y. A <a href="Topological_ordering" class="mw-redirect" title="Topological ordering">topological ordering</a> of the vertices of this DAG represents a valid reordering of the code, and the number of registers needed to evaluate the code in a given ordering is given by the vertex separation number of the ordering.<a href="#cite_note-bgt98-55">[55]</a>

For any fixed number w of machine registers, it is possible to determine in linear time whether a piece of straight-line code can be reordered in such a way that it can be evaluated with at most w registers. For, if the vertex separation number of a topological ordering is at most w, the minimum vertex separation among all orderings can be no larger, so the undirected graph formed by ignoring the orientations of the DAG described above must have pathwidth at most w. It is possible to test whether this is the case, using the known fixed-parameter-tractable algorithms for pathwidth, and if so to find a path-decomposition for the undirected graph, in linear time given the assumption that w is a constant. Once a path decomposition has been found, a topological ordering of width w (if one exists) can be found using dynamic programming, again in linear time.<a href="#cite_note-bgt98-55">[55]</a>

<div class="mw-heading mw-heading3"><h3 id="Linguistics">Linguistics</h3></div>

<a href="#CITEREFKornaiTuza1992">Kornai & Tuza (1992)</a> describe an application of path-width in <a href="Natural_language_processing" title="Natural language processing">natural language processing</a>. In this application, sentences are modeled as graphs, in which the vertices represent words and the edges represent relationships between words; for instance if an adjective modifies a noun in the sentence then the graph would have an edge between those two words. Due to the limited capacity of human short-term memory,<a href="#cite_note-56">[56]</a> Kornai and Tuza argue that this graph must have bounded pathwidth (more specifically, they argue, pathwidth at most six), for otherwise humans would not be able to parse speech correctly.

<div class="mw-heading mw-heading3"><h3 id="Exponential_algorithms">Exponential algorithms</h3></div>

Many problems in graph algorithms may be solved efficiently on graphs of low pathwidth, by using <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> on a path-decomposition of the graph.<a href="#cite_note-Arnborg_1985-10">[10]</a> For instance, if a linear ordering of the vertices of an n-vertex graph G is given, with vertex separation number w, then it is possible to find the maximum independent set of G in time O(2w n).<a href="#cite_note-fh06-31">[31]</a> On graphs of bounded pathwidth, this approach leads to fixed-parameter tractable algorithms, parametrized by the pathwidth.<a href="#cite_note-fl89-49">[49]</a> Such results are not frequently found in the literature because they are subsumed by similar algorithms parametrized by the treewidth; however, pathwidth arises even in treewidth-based dynamic programming algorithms in measuring the <a href="Space_complexity" title="Space complexity">space complexity</a> of these algorithms.<a href="#cite_note-apt00-11">[11]</a>

The same dynamic programming method also can be applied to graphs with unbounded pathwidth, leading to algorithms that solve unparametrized graph problems in <a href="Exponential_time" class="mw-redirect" title="Exponential time">exponential time</a>. For instance, combining this dynamic programming approach with the fact that cubic graphs have pathwidth n/6 + o(n) shows that, in a cubic graph, the maximum independent set can be constructed in time O(2n/6 + o(n)), faster than previous known methods.<a href="#cite_note-fh06-31">[31]</a> A similar approach leads to improved exponential-time algorithms for the <a href="Maximum_cut" title="Maximum cut">maximum cut</a> and <a href="Minimum_dominating_set" class="mw-redirect" title="Minimum dominating set">minimum dominating set</a> problems in cubic graphs,<a href="#cite_note-fh06-31">[31]</a> and for several other NP-hard optimization problems.<a href="#cite_note-57">[57]</a>

<ul><li><a href="Boxicity" title="Boxicity">Boxicity</a>, a different way of measuring the complexity of an arbitrary graph in terms of interval graphs</li>

<li><a href="Cutwidth" title="Cutwidth">Cutwidth</a>, the minimum possible width of a linear ordering of the vertices of a graph</li>

<li><a href="Tree-depth" title="Tree-depth">Tree-depth</a>, a number that is bounded for a minor-closed graph family if and only if the family excludes a path</li>

<li><a href="Degeneracy_(graph_theory)" title="Degeneracy (graph theory)">Degeneracy</a>, a measure of the sparsity of a graph that is at most equal to its path width</li>

<li><a href="Graph_bandwidth" title="Graph bandwidth">Graph bandwidth</a>, a different NP-complete optimization problem involving linear layouts of graphs</li>

<li><a href="Strahler_number" title="Strahler number">Strahler number</a>, a measure of the complexity of rooted trees defined similarly to pathwidth of unrooted trees</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#CITEREFDiestelKühn2005">Diestel & Kühn (2005)</a>.

</li>

<li id="cite_note-rs83-2">^ <a href="#cite_ref-rs83_2-0">a</a> <a href="#cite_ref-rs83_2-1">b</a> <a href="#cite_ref-rs83_2-2">c</a> <a href="#cite_ref-rs83_2-3">d</a> <a href="#CITEREFRobertsonSeymour1983">Robertson & Seymour (1983)</a>.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFKinnersley1989">Kinnersley (1989)</a>; <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>.

</li>

<li id="cite_note-Robertson_2003-4">^ <a href="#cite_ref-Robertson_2003_4-0">a</a> <a href="#cite_ref-Robertson_2003_4-1">b</a> <a href="#CITEREFRobertsonSeymour2003">Robertson & Seymour (2003)</a>.

</li>

<li id="cite_note-npc-5">^ <a href="#cite_ref-npc_5-0">a</a> <a href="#cite_ref-npc_5-1">b</a> <a href="#CITEREFKashiwabaraFujisawa1979">Kashiwabara & Fujisawa (1979)</a>; <a href="#CITEREFOhtsukiMoriKuhKashiwabara1979">Ohtsuki et al. (1979)</a>; <a href="#CITEREFLengauer1981">Lengauer (1981)</a>; <a href="#CITEREFArnborgCorneilProskurowski1987">Arnborg, Corneil & Proskurowski (1987)</a>.

</li>

<li id="cite_note-bghk92-6">^ <a href="#cite_ref-bghk92_6-0">a</a> <a href="#cite_ref-bghk92_6-1">b</a> <a href="#CITEREFBodlaenderGilbertHafsteinssonKloks1992">Bodlaender et al. (1992)</a>.

</li>

<li id="cite_note-bounded-tw-algs-7">^ <a href="#cite_ref-bounded-tw-algs_7-0">a</a> <a href="#cite_ref-bounded-tw-algs_7-1">b</a> <a href="#cite_ref-bounded-tw-algs_7-2">c</a> <a href="#CITEREFBodlaender1996">Bodlaender (1996)</a>; <a href="#CITEREFBodlaenderKloks1996">Bodlaender & Kloks (1996)</a>

</li>

<li id="cite_note-FOOTNOTEBodlaender1994-8"><a href="#cite_ref-FOOTNOTEBodlaender1994_8-0">^</a> <a href="#CITEREFBodlaender1994">Bodlaender (1994)</a>.

</li>

<li id="cite_note-tree-algs-9">^ <a href="#cite_ref-tree-algs_9-0">a</a> <a href="#cite_ref-tree-algs_9-1">b</a> <a href="#CITEREFMöhring1990">Möhring (1990)</a>; <a href="#CITEREFScheffler1990">Scheffler (1990)</a>; <a href="#CITEREFEllisSudboroughTurner1994">Ellis, Sudborough & Turner (1994)</a>; <a href="#CITEREFPengHoHsuKo1998">Peng et al. (1998)</a>; <a href="#CITEREFSkodinis2000">Skodinis (2000)</a>; <a href="#CITEREFSkodinis2003">Skodinis (2003)</a>; <a href="#CITEREFCoudertHucMazauric2012">Coudert, Huc & Mazauric (2012)</a>.

</li>

<li id="cite_note-Arnborg_1985-10">^ <a href="#cite_ref-Arnborg_1985_10-0">a</a> <a href="#cite_ref-Arnborg_1985_10-1">b</a> <a href="#CITEREFArnborg1985">Arnborg (1985)</a>.

</li>

<li id="cite_note-apt00-11">^ <a href="#cite_ref-apt00_11-0">a</a> <a href="#cite_ref-apt00_11-1">b</a> <a href="#CITEREFAspvallProskurowskiTelle2000">Aspvall, Proskurowski & Telle (2000)</a>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, Theorem 29, p. 13.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <a href="#CITEREFKinnersley1989">Kinnersley (1989)</a>; <a href="#CITEREFKinnersley1992">Kinnersley (1992)</a>; <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, Theorem 51.

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <a href="#CITEREFProskurowskiTelle1999">Proskurowski & Telle (1999)</a>.

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <a href="#CITEREFKorachSolel1993">Korach & Solel (1993)</a>, Lemma 3 p.99; <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, Theorem 47, p. 24.

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <a href="#CITEREFKorachSolel1993">Korach & Solel (1993)</a>, Lemma 1, p. 99; <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, Theorem 49, p. 24.

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <a href="#CITEREFKorachSolel1993">Korach & Solel (1993)</a>, Theorem 5, p. 99; <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, Theorem 66, p. 30. <a href="#CITEREFScheffler1992">Scheffler (1992)</a> gives a tighter upper bound of log3(2n + 1) on the pathwidth of an n-vertex forest.

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <a href="#CITEREFKorachSolel1993">Korach & Solel (1993)</a>, Theorem 6, p. 100; <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, Corollary 24, p.10.

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <a href="#CITEREFGurskiWanke2007">Gurski & Wanke (2007)</a>.

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <a href="#CITEREFGolovach1993">Golovach (1993)</a>.

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, Corollary 23, p. 10.

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, Theorem 20, p. 9.

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <a href="#CITEREFAlonSeymourThomas1990">Alon, Seymour & Thomas (1990)</a>.

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <a href="#CITEREFBodlaenderFomin2002">Bodlaender & Fomin (2002)</a>; <a href="#CITEREFCoudertHucSereni2007">Coudert, Huc & Sereni (2007)</a>.

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <a href="#CITEREFFominThilikos2007">Fomin & Thilikos (2007)</a>; <a href="#CITEREFAminiHucPérennes2009">Amini, Huc & Pérennes (2009)</a>.

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <a href="#CITEREFFomin2003">Fomin (2003)</a>.

</li>

<li id="cite_note-bm90-27">^ <a href="#cite_ref-bm90_27-0">a</a> <a href="#cite_ref-bm90_27-1">b</a> <a href="#CITEREFBodlaenderMöhring1990">Bodlaender & Möhring (1990)</a>.

</li>

<li id="cite_note-bkk93-28">^ <a href="#cite_ref-bkk93_28-0">a</a> <a href="#cite_ref-bkk93_28-1">b</a> <a href="#CITEREFBodlaenderKloksKratsch1993">Bodlaender, Kloks & Kratsch (1993)</a>.

</li>

<li id="cite_note-hm94-29">^ <a href="#cite_ref-hm94_29-0">a</a> <a href="#cite_ref-hm94_29-1">b</a> <a href="#CITEREFHabibMöhring1994">Habib & Möhring (1994)</a>.

</li>

<li id="cite_note-g95-30">^ <a href="#cite_ref-g95_30-0">a</a> <a href="#cite_ref-g95_30-1">b</a> <a href="#CITEREFGarbe1995">Garbe (1995)</a>.

</li>

<li id="cite_note-fh06-31">^ <a href="#cite_ref-fh06_31-0">a</a> <a href="#cite_ref-fh06_31-1">b</a> <a href="#cite_ref-fh06_31-2">c</a> <a href="#cite_ref-fh06_31-3">d</a> <a href="#CITEREFFominHøie2006">Fomin & Høie (2006)</a>.

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <a href="#CITEREFFominKratschTodincaVillanger2008">Fomin et al. (2008)</a>.

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <a href="#CITEREFDowneyFellows1999">Downey & Fellows (1999)</a>, p.12.

</li>

<li id="cite_note-ms88-34">^ <a href="#cite_ref-ms88_34-0">a</a> <a href="#cite_ref-ms88_34-1">b</a> <a href="#cite_ref-ms88_34-2">c</a> <a href="#cite_ref-ms88_34-3">d</a> <a href="#CITEREFMonienSudborough1988">Monien & Sudborough (1988)</a>.

</li>

<li id="cite_note-35"><a href="#cite_ref-35">^</a> <a href="#CITEREFGustedt1993">Gustedt (1993)</a>.

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> <a href="#CITEREFKloksKratschMüller1995">Kloks, Kratsch & Müller (1995)</a>. A chordal domino is a chordal graph in which every vertex belongs to at most two maximal cliques.

</li>

<li id="cite_note-kbmk-37">^ <a href="#cite_ref-kbmk_37-0">a</a> <a href="#cite_ref-kbmk_37-1">b</a> <a href="#CITEREFKloksBodlaenderMüllerKratsch1993">Kloks et al. (1993)</a>.

</li>

<li id="cite_note-38"><a href="#cite_ref-38">^</a> <a href="#CITEREFKloksBodlaender1992">Kloks & Bodlaender (1992)</a>; <a href="#CITEREFGustedt1993">Gustedt (1993)</a>.

</li>

<li id="cite_note-39"><a href="#cite_ref-39">^</a> <a href="#CITEREFGarbe1995">Garbe (1995)</a> credits this result to the 1993 Ph.D. thesis of Ton Kloks; Garbe's polynomial time algorithm for comparability graphs of interval orders generalizes this result, since any chordal graph must be a comparability graph of this type.

</li>

<li id="cite_note-40"><a href="#cite_ref-40">^</a> <a href="#CITEREFSuchanTodinca2007">Suchan & Todinca (2007)</a>.

</li>

<li id="cite_note-41"><a href="#cite_ref-41">^</a> <a href="#CITEREFFeigeHajiaghayiLee2005">Feige, Hajiaghayi & Lee (2005)</a>.

</li>

<li id="cite_note-gm20-42">^ <a href="#cite_ref-gm20_42-0">a</a> <a href="#cite_ref-gm20_42-1">b</a> <a href="#CITEREFRobertsonSeymour2004">Robertson & Seymour (2004)</a>.

</li>

<li id="cite_note-43"><a href="#cite_ref-43">^</a> <a href="#CITEREFBienstockRobertsonSeymourThomas1991">Bienstock et al. (1991)</a>; <a href="#CITEREFDiestel1995">Diestel (1995)</a>; <a href="#CITEREFCattellDinneenFellows1996">Cattell, Dinneen & Fellows (1996)</a>.

</li>

<li id="cite_note-obstructions-44">^ <a href="#cite_ref-obstructions_44-0">a</a> <a href="#cite_ref-obstructions_44-1">b</a> <a href="#CITEREFKinnersley1992">Kinnersley (1992)</a>; <a href="#CITEREFTakahashiUenoKajitani1994">Takahashi, Ueno & Kajitani (1994)</a>; <a href="#CITEREFBodlaender1998">Bodlaender (1998)</a>, p. 8.

</li>

<li id="cite_note-45"><a href="#cite_ref-45">^</a> <a href="#CITEREFKinnersleyLangston1994">Kinnersley & Langston (1994)</a>.

</li>

<li id="cite_note-46"><a href="#cite_ref-46">^</a> <a href="#CITEREFDemaineHajiaghayiKawarabayashi2005">Demaine, Hajiaghayi & Kawarabayashi (2005)</a>.

</li>

<li id="cite_note-47"><a href="#cite_ref-47">^</a> <a href="#CITEREFBerge1967">Berge (1967)</a>.

</li>

<li id="cite_note-48"><a href="#cite_ref-48">^</a> <a href="#CITEREFLopezLaw1980">Lopez & Law (1980)</a>.

</li>

<li id="cite_note-fl89-49">^ <a href="#cite_ref-fl89_49-0">a</a> <a href="#cite_ref-fl89_49-1">b</a> <a href="#CITEREFFellowsLangston1989">Fellows & Langston (1989)</a>.

</li>

<li id="cite_note-50"><a href="#cite_ref-50">^</a> <a href="#CITEREFMöhring1990">Möhring (1990)</a>; <a href="#CITEREFFerreiraSong1992">Ferreira & Song (1992)</a>.

</li>

<li id="cite_note-h03-51"><a href="#cite_ref-h03_51-0">^</a> <a href="#CITEREFHliněny2003">Hliněny (2003)</a>.

</li>

<li id="cite_note-52"><a href="#cite_ref-52">^</a> <a href="#CITEREFSuderman2004">Suderman (2004)</a>.

</li>

<li id="cite_note-dfkl08-53"><a href="#cite_ref-dfkl08_53-0">^</a> <a href="#CITEREFDujmovićFellowsKitchingLiotta2008">Dujmović et al. (2008)</a>.

</li>

<li id="cite_note-54"><a href="#cite_ref-54">^</a> <a href="#CITEREFDujmovićMorinWood2003">Dujmović, Morin & Wood (2003)</a>.

</li>

<li id="cite_note-bgt98-55">^ <a href="#cite_ref-bgt98_55-0">a</a> <a href="#cite_ref-bgt98_55-1">b</a> <a href="#CITEREFBodlaenderGustedtTelle1998">Bodlaender, Gustedt & Telle (1998)</a>.

</li>

<li id="cite_note-56"><a href="#cite_ref-56">^</a> <a href="#CITEREFMiller1956">Miller (1956)</a>.

</li>

<li id="cite_note-57"><a href="#cite_ref-57">^</a> <a href="#CITEREFKneisMölleRichterRossmanith2005">Kneis et al. (2005)</a>; <a href="#CITEREFBjörklundHusfeldt2008">Björklund & Husfeldt (2008)</a>.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin refbegin-columns references-column-width" style="column-width: 30em">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAlonSeymourThomas1990" class="citation cs2"><a href="Noga_Alon" title="Noga Alon">Alon, Noga</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul</a>; <a href="Robin_Thomas_(mathematician)" title="Robin Thomas (mathematician)">Thomas, Robin</a> (1990), "A separator theorem for graphs with an excluded minor and its applications", Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990), pp. 293–299, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F100216.100254">10.1145/100216.100254</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0897913612</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17521329">17521329</a></cite>.</li>

<li><cite id="CITEREFAminiHucPérennes2009" class="citation cs2">Amini, Omid; Huc, Florian; Pérennes, Stéphane (2009), "On the path-width of planar graphs", <a href="SIAM_Journal_on_Discrete_Mathematics" title="SIAM Journal on Discrete Mathematics">SIAM Journal on Discrete Mathematics</a>, 23 (3): 1311–1316, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F060670146">10.1137/060670146</a></cite>.</li>

<li><cite id="CITEREFArnborg1985" class="citation cs2">Arnborg, Stefan (1985), "Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey", BIT, 25 (1): 2–23, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01934985">10.1007/BF01934985</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122263659">122263659</a></cite>.</li>

<li><cite id="CITEREFArnborgCorneilProskurowski1987" class="citation cs2">Arnborg, Stefan; <a href="Derek_Corneil" title="Derek Corneil">Corneil, Derek G.</a>; Proskurowski, Andrzej (1987), "Complexity of finding embeddings in a k-tree", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 277–284, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0608024">10.1137/0608024</a></cite>.</li>

<li><cite id="CITEREFAspvallProskurowskiTelle2000" class="citation cs2">Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne (2000), "Memory requirements for table computations in partial k-tree algorithms", <a href="Algorithmica" title="Algorithmica">Algorithmica</a>, 27 (3): 382–394, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs004530010025">10.1007/s004530010025</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9690525">9690525</a></cite>.</li>

<li><cite id="CITEREFBerge1967" class="citation cs2"><a href="Claude_Berge" title="Claude Berge">Berge, Claude</a> (1967), "Some classes of perfect graphs", Graph Theory and Theoretical Physics, New York: Academic Press, pp. 155–165</cite>.</li>

<li><cite id="CITEREFBienstockRobertsonSeymourThomas1991" class="citation cs2">Bienstock, Dan; <a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul</a>; <a href="Robin_Thomas_(mathematician)" title="Robin Thomas (mathematician)">Thomas, Robin</a> (1991), "Quickly excluding a forest", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory, Series B</a>, 52 (2): 274–283, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0095-8956%2891%2990068-U">10.1016/0095-8956(91)90068-U</a></cite>.</li>

<li><cite id="CITEREFBjörklundHusfeldt2008" class="citation cs2">Björklund, Andreas; Husfeldt, Thore (2008), "Exact algorithms for exact satisfiability and number of perfect matchings", <a href="Algorithmica" title="Algorithmica">Algorithmica</a>, 52 (2): 226–249, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-007-9149-8">10.1007/s00453-007-9149-8</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:37693881">37693881</a></cite>.</li>

<li><cite id="CITEREFBodlaender1994" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a> (1994), "A tourist guide through treewidth", in Dassow, Jürgen; Kelemenová, Alisa (eds.), Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992), Topics in Computer Mathematics, vol. 6, Gordon and Breach, pp. 1–20</cite>.</li>

<li><cite id="CITEREFBodlaender1994a" class="citation journal cs2">Bodlaender, Hans L. (1994a), "A tourist guide through treewidth", Acta Cybernetica, 11: 1–2</cite></li>

<li><cite id="CITEREFBodlaender1996" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a> (1996), "A linear-time algorithm for finding tree-decompositions of small treewidth", <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>, 25 (6): 1305–1317, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539793251219">10.1137/S0097539793251219</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1874%2F16670">1874/16670</a></cite>.</li>

<li><cite id="CITEREFBodlaender1998" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a> (1998), "A partial k-arboretum of graphs with bounded treewidth", <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>, 209 (1–2): 1–45, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-3975%2897%2900228-4">10.1016/S0304-3975(97)00228-4</a></cite>.</li>

<li><cite id="CITEREFBodlaenderFomin2002" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a>; Fomin, Fedor V. (2002), "Approximation of pathwidth of outerplanar graphs", Journal of Algorithms, 43 (2): 190–200, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0196-6774%2802%2900001-9">10.1016/S0196-6774(02)00001-9</a></cite>.</li>

<li><cite id="CITEREFBodlaenderGilbertHafsteinssonKloks1992" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a>; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1992), "Approximating treewidth, pathwidth, and minimum elimination tree height", Graph-Theoretic Concepts in Computer Science, <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>, vol. 570, pp. 1–12, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-55121-2_1">10.1007/3-540-55121-2_1</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1874%2F17927">1874/17927</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-55121-8</bdi></cite>.</li>

<li><cite id="CITEREFBodlaenderGustedtTelle1998" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a>; Gustedt, Jens; Telle, Jan Arne (1998), "Linear-time register allocation for a fixed number of registers", <a rel="nofollow" class="external text" href="http://www.ii.uib.no/~telle/bib/BGT.pdf">Proc. 9th ACM–SIAM Symposium on Discrete Algorithms (SODA '98)</a> (PDF), pp. 574–583</cite>.</li>

<li><cite id="CITEREFBodlaenderKloks1996" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a>; Kloks, Ton (1996), "Efficient and constructive algorithms for the pathwidth and treewidth of graphs", Journal of Algorithms, 21 (2): 358–402, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjagm.1996.0049">10.1006/jagm.1996.0049</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1874%2F16538">1874/16538</a></cite>.</li>

<li><cite id="CITEREFBodlaenderKloksKratsch1993" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a>; Kloks, Ton; Kratsch, Dieter (1993), "Treewidth and pathwidth of permutation graphs", <a href="International_Colloquium_on_Automata%2C_Languages_and_Programming" title="International Colloquium on Automata, Languages and Programming">Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993)</a>, Lecture Notes in Computer Science, vol. 700, Springer-Verlag, pp. 114–125, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-56939-1_66">10.1007/3-540-56939-1_66</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1874%2F16657">1874/16657</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-56939-8</bdi></cite>.</li>

<li><cite id="CITEREFBodlaenderMöhring1990" class="citation cs2"><a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a>; Möhring, Rolf H. (1990), "The pathwidth and treewidth of cographs", <a href="SWAT_and_WADS_conferences" title="SWAT and WADS conferences">Proc. 2nd Scandinavian Workshop on Algorithm Theory</a>, Lecture Notes in Computer Science, vol. 447, Springer-Verlag, pp. 301–309, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-52846-6_99">10.1007/3-540-52846-6_99</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1874%2F16625">1874/16625</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-52846-3</bdi></cite>.</li>

<li><cite id="CITEREFCattellDinneenFellows1996" class="citation cs2">Cattell, Kevin; Dinneen, Michael J.; <a href="Michael_Fellows" title="Michael Fellows">Fellows, Michael R.</a> (1996), "A simple linear-time algorithm for finding path-decompositions of small width", <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>, 57 (4): 197–203, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/9410211">math/9410211</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2895%2900190-5">10.1016/0020-0190(95)00190-5</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2442557">2442557</a></cite>.</li>

<li><cite id="CITEREFCoudertHucMazauric2012" class="citation cs2">Coudert, David; Huc, Florian; Mazauric, Dorian (2012), <a rel="nofollow" class="external text" href="https://hal.inria.fr/inria-00587819/file/paper-noformat.pdf">"A Distributed Algorithm for Computing the Node Search Number in Trees"</a> (PDF), <a href="Algorithmica" title="Algorithmica">Algorithmica</a>, 63 (1): 158–190, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-011-9524-3">10.1007/s00453-011-9524-3</a></cite>.</li>

<li><cite id="CITEREFCoudertHucSereni2007" class="citation cs2">Coudert, David; Huc, Florian; Sereni, Jean-Sébastien (2007), <a rel="nofollow" class="external text" href="https://hal.inria.fr/inria-00070220/file/RR-5804.pdf">"Pathwidth of outerplanar graphs"</a> (PDF), <a href="Journal_of_Graph_Theory" title="Journal of Graph Theory">Journal of Graph Theory</a>, 55 (1): 27–41, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fjgt.20218">10.1002/jgt.20218</a></cite>.</li>

<li><cite id="CITEREFDiestel1995" class="citation cs2">Diestel, Reinhard (1995), "Graph Minors I: a short proof of the path-width theorem", <a href="Combinatorics%2C_Probability_and_Computing" title="Combinatorics, Probability and Computing">Combinatorics, Probability and Computing</a>, 4 (1): 27–30, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0963548300001450">10.1017/S0963548300001450</a></cite>.</li>

<li><cite id="CITEREFDiestelKühn2005" class="citation cs2">Diestel, Reinhard; <a href="Daniela_K%C3%BChn" title="Daniela Kühn">Kühn, Daniela</a> (2005), "Graph minor hierarchies", <a href="Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a>, 145 (2): 167–182, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2004.01.010">10.1016/j.dam.2004.01.010</a></cite>.</li>

<li><cite id="CITEREFDemaineHajiaghayiKawarabayashi2005" class="citation cs2"><a href="Erik_Demaine" title="Erik Demaine">Demaine, Erik D.</a>; <a href="Mohammad_Hajiaghayi" title="Mohammad Hajiaghayi">Hajiaghayi, MohammadTaghi</a>; <a href="Ken-ichi_Kawarabayashi" title="Ken-ichi Kawarabayashi">Kawarabayashi, Ken-ichi</a> (2005), "Algorithmic graph minor theory: decomposition, approximation, and coloring", <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005)</a>, pp. 637–646, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.2005.14">10.1109/SFCS.2005.14</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7695-2468-0</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13238254">13238254</a></cite>.</li>

<li><cite id="CITEREFDowneyFellows1999" class="citation cs2"><a href="Rod_Downey" title="Rod Downey">Downey, Rod G.</a>; <a href="Michael_Fellows" title="Michael Fellows">Fellows, Michael R.</a> (1999), Parameterized Complexity, Springer-Verlag, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-94883-X</bdi></cite>.</li>

<li><cite id="CITEREFDujmovićFellowsKitchingLiotta2008" class="citation cs2"><a href="Vida_Dujmovi%C4%87" title="Vida Dujmović">Dujmović, V.</a>; <a href="Michael_Fellows" title="Michael Fellows">Fellows, M.R.</a>; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; <a href="Sue_Whitesides" title="Sue Whitesides">Whitesides, S.</a>; <a href="David_Wood_(mathematician)" title="David Wood (mathematician)">Wood, David R.</a> (2008), "On the parameterized complexity of layered graph drawing", <a href="Algorithmica" title="Algorithmica">Algorithmica</a>, 52 (2): 267–292, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-007-9151-1">10.1007/s00453-007-9151-1</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2298634">2298634</a></cite>.</li>

<li><cite id="CITEREFDujmovićMorinWood2003" class="citation cs2"><a href="Vida_Dujmovi%C4%87" title="Vida Dujmović">Dujmović, Vida</a>; <a href="Pat_Morin" title="Pat Morin">Morin, Pat</a>; <a href="David_Wood_(mathematician)" title="David Wood (mathematician)">Wood, David R.</a> (2003), <a rel="nofollow" class="external text" href="http://cg.scs.carleton.ca/~vida/pubs/papers/DMW-GD02.pdf">"Path-width and three-dimensional straight-line grid drawings of graphs"</a> (PDF), <a href="International_Symposium_on_Graph_Drawing" title="International Symposium on Graph Drawing">Proc. 10th International Symposium on Graph Drawing (GD 2002)</a>, Lecture Notes in Computer Science, vol. 2528, Springer-Verlag, pp. 42–53</cite>.</li>

<li><cite id="CITEREFEllisSudboroughTurner1983" class="citation cs2">Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1983), "Graph separation and search number", Proc. 1983 Allerton Conf. on Communication, Control, and Computing</cite>. As cited by <a href="#CITEREFMonienSudborough1988">Monien & Sudborough (1988)</a>.</li>

<li><cite id="CITEREFEllisSudboroughTurner1994" class="citation cs2">Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1994), "The vertex separation and search number of a tree", <a href="Information_and_Computation" title="Information and Computation">Information and Computation</a>, 113 (1): 50–79, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Finco.1994.1064">10.1006/inco.1994.1064</a></cite>.</li>

<li><cite id="CITEREFFeigeHajiaghayiLee2005" class="citation cs2"><a href="Uriel_Feige" title="Uriel Feige">Feige, Uriel</a>; <a href="Mohammad_Hajiaghayi" title="Mohammad Hajiaghayi">Hajiaghayi, Mohammadtaghi</a>; Lee, James R. (2005), "Improved approximation algorithms for minimum-weight vertex separators", <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Proc. 37th ACM Symposium on Theory of Computing (STOC 2005)</a>, pp. 563–572, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1060590.1060674">10.1145/1060590.1060674</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1581139608</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14097859">14097859</a></cite>.</li>

<li><cite id="CITEREFFellowsLangston1989" class="citation cs2"><a href="Michael_Fellows" title="Michael Fellows">Fellows, Michael R.</a>; <a href="Michael_Langston" title="Michael Langston">Langston, Michael A.</a> (1989), "On search decision and the efficiency of polynomial-time algorithms", <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Proc. 21st ACM Symposium on Theory of Computing</a>, pp. 501–512, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F73007.73055">10.1145/73007.73055</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0897913078</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1854173">1854173</a></cite>.</li>

<li><cite id="CITEREFFerreiraSong1992" class="citation cs2">Ferreira, Afonso G.; Song, Siang W. (1992), "Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach", Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92), Lecture Notes in Computer Science, vol. 583, Springer-Verlag, pp. 139–153, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0023825">10.1007/BFb0023825</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10068%2F43314">10068/43314</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-55284-7</bdi></cite>.</li>

<li><cite id="CITEREFde_Fluiter1997" class="citation cs2">de Fluiter, Babette (1997), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110724173550/http://igitur-archive.library.uu.nl/dissertations/01847381/full.pdf">Algorithms for Graphs of Small Treewidth</a> (PDF), Ph.D. thesis, <a href="Utrecht_University" title="Utrecht University">Utrecht University</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>90-393-1528-0</bdi>, archived from <a rel="nofollow" class="external text" href="http://igitur-archive.library.uu.nl/dissertations/01847381/full.pdf">the original</a> (PDF) on 2011-07-24, retrieved 2010-05-06</cite>.</li>

<li><cite id="CITEREFFomin2003" class="citation cs2">Fomin, Fedor V. (2003), "Pathwidth of planar and line graphs", <a href="Graphs_and_Combinatorics" title="Graphs and Combinatorics">Graphs and Combinatorics</a>, 19 (1): 91–99, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00373-002-0490-z">10.1007/s00373-002-0490-z</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:43123449">43123449</a></cite>.</li>

<li><cite id="CITEREFFominHøie2006" class="citation cs2">Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms", <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>, 97 (5): 191–196, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ipl.2005.10.012">10.1016/j.ipl.2005.10.012</a></cite>.</li>

<li><cite id="CITEREFFominKratschTodincaVillanger2008" class="citation cs2">Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve (2008), "Exact algorithms for treewidth and minimum fill-in", <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>, 38 (3): 1058–1079, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F050643350">10.1137/050643350</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1956%2F1151">1956/1151</a></cite>.</li>

<li><cite id="CITEREFFominThilikos2007" class="citation cs2">Fomin, Fedor V.; Thilikos, Dimitrios M. (2007), "On self duality of pathwidth in polyhedral graph embeddings", <a href="Journal_of_Graph_Theory" title="Journal of Graph Theory">Journal of Graph Theory</a>, 55 (1): 42–54, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fjgt.20219">10.1002/jgt.20219</a></cite>.</li>

<li><cite id="CITEREFGarbe1995" class="citation cs2">Garbe, Renate (1995), "Tree-width and path-width of comparability graphs of interval orders", Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), Lecture Notes in Computer Science, vol. 903, Springer-Verlag, pp. 26–37, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-59071-4_35">10.1007/3-540-59071-4_35</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-59071-2</bdi></cite>.</li>

<li><cite id="CITEREFGolovach1993" class="citation cs2">Golovach, P. A. (1993), "The cutwidth of a graph and the vertex separation number of the line graph", Discrete Mathematics and Applications, 3 (5): 517–522, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1515%2Fdma.1993.3.5.517">10.1515/dma.1993.3.5.517</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:120745961">120745961</a></cite>.</li>

<li><cite id="CITEREFGuha2000" class="citation cs2">Guha, Sudipto (2000), "Nested graph dissection and approximation algorithms", <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000)</a>, p. 126, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.2000.892072">10.1109/SFCS.2000.892072</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7695-0850-2</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9854056">9854056</a></cite>.</li>

<li><cite id="CITEREFGurskiWanke2007" class="citation cs2">Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 307 (22): 2734–2754, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2007.01.020">10.1016/j.disc.2007.01.020</a></cite>.</li>

<li><cite id="CITEREFGustedt1993" class="citation cs2">Gustedt, Jens (1993), "On the pathwidth of chordal graphs", <a href="Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a>, 45 (3): 233–248, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0166-218X%2893%2990012-D">10.1016/0166-218X(93)90012-D</a></cite>.</li>

<li><cite id="CITEREFHabibMöhring1994" class="citation cs2">Habib, Michel; Möhring, Rolf H. (1994), "Treewidth of cocomparability graphs and a new order-theoretic parameter", <a href="Order_(journal)" title="Order (journal)">Order</a>, 11 (1): 47–60, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01462229">10.1007/BF01462229</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2648030">2648030</a></cite>.</li>

<li><cite id="CITEREFHliněny2003" class="citation cs2">Hliněny, Petr (2003), "Crossing-number critical graphs have bounded path-width", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory, Series B</a>, 88 (2): 347–367, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0095-8956%2803%2900037-6">10.1016/S0095-8956(03)00037-6</a></cite>.</li>

<li><cite id="CITEREFKashiwabaraFujisawa1979" class="citation cs2">Kashiwabara, T.; Fujisawa, T. (1979), "NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph", <a href="International_Symposium_on_Circuits_and_Systems" class="mw-redirect" title="International Symposium on Circuits and Systems">Proc. International Symposium on Circuits and Systems</a>, pp. 657–660</cite>.</li>

<li><cite id="CITEREFKinnersley1989" class="citation cs2">Kinnersley, Nancy G. (1989), Obstruction set isolation for layout permutation problems (Ph.D. thesis), Washington State University, <a href="ProQuest" title="ProQuest">ProQuest</a> <a rel="nofollow" class="external text" href="https://www.proquest.com/docview/303738168">303738168</a></cite>; see Theorem 6.A, p. 44.</li>

<li><cite id="CITEREFKinnersley1992" class="citation cs2">Kinnersley, Nancy G. (1992), "The vertex separation number of a graph equals its path-width", <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>, 42 (6): 345–350, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2892%2990234-M">10.1016/0020-0190(92)90234-M</a></cite>.</li>

<li><cite id="CITEREFKinnersleyLangston1994" class="citation cs2">Kinnersley, Nancy G.; <a href="Michael_Langston" title="Michael Langston">Langston, Michael A.</a> (1994), "Obstruction set isolation for the gate matrix layout problem", <a href="Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a>, 54 (2–3): 169–213, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0166-218X%2894%2990021-3">10.1016/0166-218X(94)90021-3</a></cite>.</li>

<li><cite id="CITEREFKirousisPapadimitriou1985" class="citation cs2">Kirousis, Lefteris M.; <a href="Christos_Papadimitriou" title="Christos Papadimitriou">Papadimitriou, Christos H.</a> (1985), "Interval graphs and searching", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 55 (2): 181–184, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2885%2990046-9">10.1016/0012-365X(85)90046-9</a></cite>.</li>

<li><cite id="CITEREFKloksBodlaender1992" class="citation cs2">Kloks, Ton; <a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a> (1992), "Approximating treewidth and pathwidth of some classes of perfect graphs", Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92), Lecture Notes in Computer Science, vol. 650, Springer-Verlag, pp. 116–125, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-56279-6_64">10.1007/3-540-56279-6_64</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1874%2F16672">1874/16672</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-56279-5</bdi></cite>.</li>

<li><cite id="CITEREFKloksBodlaenderMüllerKratsch1993" class="citation cs2">Kloks, T.; <a href="Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, H.</a>; Müller, H.; Kratsch, D. (1993), "Computing treewidth and minimum fill-in: all you need are the minimal separators", <a href="European_Symposium_on_Algorithms" title="European Symposium on Algorithms">Proc. 1st European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science)</a>, vol. 726, Springer-Verlag, pp. 260–271, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-57273-2_61">10.1007/3-540-57273-2_61</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-57273-2</bdi></cite>.</li>

<li><cite id="CITEREFKloksKratschMüller1995" class="citation cs2">Kloks, Ton; Kratsch, Dieter; Müller, H. (1995), "Dominoes", Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), Lecture Notes in Computer Science, vol. 903, Springer-Verlag, pp. 106–120, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-59071-4_41">10.1007/3-540-59071-4_41</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-59071-2</bdi></cite>.</li>

<li><cite id="CITEREFKneisMölleRichterRossmanith2005" class="citation cs2">Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter (2005), "Algorithms based on the treewidth of sparse graphs", Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, pp. 385–396, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11604686_34">10.1007/11604686_34</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-31000-6</bdi></cite>.</li>

<li><cite id="CITEREFKorachSolel1993" class="citation cs2">Korach, Ephraim; Solel, Nir (1993), "Tree-width, path-width, and cutwidth", <a href="Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a>, 43 (1): 97–101, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0166-218X%2893%2990171-J">10.1016/0166-218X(93)90171-J</a></cite>.</li>

<li><cite id="CITEREFKornaiTuza1992" class="citation cs2">Kornai, András; Tuza, Zsolt (1992), "Narrowness, path-width, and their application in natural language processing", <a href="Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a>, 36 (1): 87–92, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0166-218X%2892%2990208-R">10.1016/0166-218X(92)90208-R</a></cite>.</li>

<li><cite id="CITEREFLengauer1981" class="citation cs2">Lengauer, Thomas (1981), "Black-white pebbles and graph separation", <a href="Acta_Informatica" title="Acta Informatica">Acta Informatica</a>, 16 (4): 465–475, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00264496">10.1007/BF00264496</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:19415148">19415148</a></cite>.</li>

<li><cite id="CITEREFLopezLaw1980" class="citation cs2">Lopez, Alexander D.; Law, Hung-Fai S. (1980), "A dense gate matrix layout method for MOS VLSI", IEEE Transactions on Electron Devices, 27 (8): 1671–1675, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1980ITED...27.1671L">1980ITED...27.1671L</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FT-ED.1980.20086">10.1109/T-ED.1980.20086</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:64469353">64469353</a>, Also in the joint issue, IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980</cite>.</li>

<li><cite id="CITEREFMiller1956" class="citation cs2"><a href="George_Armitage_Miller" title="George Armitage Miller">Miller, George A.</a> (1956), <a rel="nofollow" class="external text" href="http://www.musanim.com/miller1956/">"The Magical Number Seven, Plus or Minus Two"</a>, <a href="Psychological_Review" title="Psychological Review">Psychological Review</a>, 63 (2): 81–97, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1037%2Fh0043158">10.1037/h0043158</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/11858%2F00-001M-0000-002C-4646-B">11858/00-001M-0000-002C-4646-B</a>, <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/13310704">13310704</a></cite>.</li>

<li><cite id="CITEREFMöhring1990" class="citation cs2">Möhring, Rolf H. (1990), "Graph problems related to gate matrix layout and PLA folding", in Tinhofer, G.; Mayr, E.; Noltemeier, H.; et al. (eds.), Computational Graph Theory, Computing Supplementum, vol. 7, Springer-Verlag, pp. 17–51, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-211-82177-5</bdi></cite>.</li>

<li><cite id="CITEREFMonienSudborough1988" class="citation cs2">Monien, B.; Sudborough, I. H. (1988), "Min cut is NP-complete for edge weighted trees", <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>, 58 (1–3): 209–229, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2888%2990028-X">10.1016/0304-3975(88)90028-X</a></cite>.</li>

<li><cite id="CITEREFOhtsukiMoriKuhKashiwabara1979" class="citation cs2">Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979), "One-dimensional logic gate assignment and interval graphs", IEEE Transactions on Circuits and Systems, 26 (9): 675–684, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTCS.1979.1084695">10.1109/TCS.1979.1084695</a></cite>.</li>

<li><cite id="CITEREFPengHoHsuKo1998" class="citation cs2">Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi (1998), "A linear-time algorithm for constructing an optimal node-search strategy of a tree", in Hsu, Wen-Lian; Kao, Ming-Yang (eds.), Computing and Combinatorics, 4th Annual International Conference, COCOON '98, Taipei, Taiwan, R.o.C., August 12–14, 1998, Proceedings, Lecture Notes in Computer Science, vol. 1449, Springer, pp. 279–288, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-68535-9_32">10.1007/3-540-68535-9_32</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-64824-6</bdi></cite></li>

<li><cite id="CITEREFProskurowskiTelle1999" class="citation cs2">Proskurowski, Andrzej; Telle, Jan Arne (1999), <a rel="nofollow" class="external text" href="http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf">"Classes of graphs with restricted interval models"</a> (PDF), Discrete Mathematics and Theoretical Computer Science, 3: 167–176</cite>.</li>

<li><cite id="CITEREFRobertsonSeymour1983" class="citation cs2"><a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul</a> (1983), "Graph minors. I. Excluding a forest", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory, Series B</a>, 35 (1): 39–61, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0095-8956%2883%2990079-5">10.1016/0095-8956(83)90079-5</a></cite>.</li>

<li><cite id="CITEREFRobertsonSeymour2003" class="citation cs2"><a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul</a> (2003), "Graph minors. XVI. Excluding a non-planar graph", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory, Series B</a>, 89 (1): 43–76, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0095-8956%2803%2900042-X">10.1016/S0095-8956(03)00042-X</a></cite>.</li>

<li><cite id="CITEREFRobertsonSeymour2004" class="citation cs2"><a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul D.</a> (2004), "Graph Minors. XX. Wagner's conjecture", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory, Series B</a>, 92 (2): 325–357, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jctb.2004.08.001">10.1016/j.jctb.2004.08.001</a></cite>.</li>

<li><cite id="CITEREFScheffler1990" class="citation cs2">Scheffler, Petra (1990), "A linear algorithm for the pathwidth of trees", in Bodendiek, R.; Henn, R. (eds.), Topics in Combinatorics and Graph Theory, Physica-Verlag, pp. 613–620</cite>.</li>

<li><cite id="CITEREFScheffler1992" class="citation cs2">Scheffler, Petra (1992), "Optimal embedding of a tree into an interval graph in linear time", in <a href="Jaroslav_Ne%C5%A1et%C5%99il" title="Jaroslav Nešetřil">Nešetřil, Jaroslav</a>; Fiedler, Miroslav (eds.), Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, Elsevier</cite>.</li>

<li><cite id="CITEREFSkodinis2000" class="citation cs2">Skodinis, Konstantin (2000), "Computing optimal linear layouts of trees in linear time", <a href="European_Symposium_on_Algorithms" title="European Symposium on Algorithms">Proc. 8th European Symposium on Algorithms (ESA 2000)</a>, Lecture Notes in Computer Science, vol. 1879, Springer-Verlag, pp. 403–414, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45253-2_37">10.1007/3-540-45253-2_37</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-41004-1</bdi></cite>.</li>

<li><cite id="CITEREFSkodinis2003" class="citation cs2">Skodinis, Konstantin (2003), "Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time", Journal of Algorithms, 47 (1): 40–59, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0196-6774%2802%2900225-0">10.1016/S0196-6774(02)00225-0</a></cite>.</li>

<li><cite id="CITEREFSuchanTodinca2007" class="citation cs2">Suchan, Karol; Todinca, Ioan (2007), "Pathwidth of circular-arc graphs", Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), Lecture Notes in Computer Science, vol. 4769, Springer-Verlag, pp. 258–269, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-74839-7_25">10.1007/978-3-540-74839-7_25</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-74838-0</bdi></cite>.</li>

<li><cite id="CITEREFSuderman2004" class="citation cs2">Suderman, Matthew (2004), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20030503103911/http://cgm.cs.mcgill.ca/~msuder/schools/mcgill/research/trees/SOCS-02-8.pdf">"Pathwidth and layered drawings of trees"</a> (PDF), <a href="International_Journal_of_Computational_Geometry_and_Applications" title="International Journal of Computational Geometry and Applications">International Journal of Computational Geometry and Applications</a>, 14 (3): 203–225, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2FS0218195904001433">10.1142/S0218195904001433</a>, archived from <a rel="nofollow" class="external text" href="http://cgm.cs.mcgill.ca/~msuder/schools/mcgill/research/trees/SOCS-02-8.pdf">the original</a> (PDF) on 2003-05-03</cite>.</li>

<li><cite id="CITEREFTakahashiUenoKajitani1994" class="citation cs2">Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji (1994), "Minimal acyclic forbidden minors for the family of graphs with bounded path-width", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 127 (1–3): 293–304, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2894%2990092-2">10.1016/0012-365X(94)90092-2</a></cite>.</li></ul>

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-05" href="https://en.wikipedia.org/wiki/?title=Pathwidth&oldid=1278937763">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>